The present invention relates to a method and apparatus for contouring gridded data. The invention is particularly useful in preparing topographical maps, and is therefore described below with respect to this application.
Contour lines are lines of a common or equal value along the Z-axis of a three-dimensional object, and are commonly used to describe graphically the surface of the three-dimensional object. Contour maps are thus two dimensional representations of three dimensional surfaces of the form Z=f(x,y). Various algorithms exist for computing contour maps, many of which are summarized in the survey papers of Sutcliffe, D.C., Contouring Over Rectangular and Skewed Rectangular Grids--An Introduction, in Mathematical Methods in Computer Graphics and Design, K. Brodlie (ed.), Academic Press, New York, 1980, 39-62; and Sabin, M.D., A Survey of Contouring Methods, Computer Graphics Forum 5 (1986), 325-340. The most common example of a contour map is a topographic map, wherein a contour line of elevation "H" is the line connecting all points on the surface whose elevation (long the Z-axis) is equal to "H".
There are a number of known methods to create contour lines. One method involves direct measurement, e.g., using stereo-aerial photographic techniques, in which elevations are measured, and the contour of lines are drawn through direct and continuous measurements by a human operator. Another method is through ground survey measuring points, this method involving interpolation between the sample points to define the contour line of any specified elevation.
A third known technique involves measurement of the elevation of the surface, e.g., by stereo pair aerial photography, at regular spacings along the X and Y-axes, resulting in a set of points on a grid of equal sides each of which has a measured elevation along the Z-axis. The contour lines are then generated from these elevation points by interpolating the measured values to the required contour line value. For example, if the preselected elevation H (value along the Z-axis) is 10.0 meters, the contour lines will connect all points on the grid lines having an elevation of 10.0 meters.
The present invention is concerned with the technique of the third type described above for contouring gridded data. The third technique for generating contour lines is generally more efficient than either of the above-described first or second techniques, but involves solving a problem, sometimes called the "degenerate cell", arising as follows: